const _ = require('underscore')
var cfg = require('./config')
cfg.K = cfg.dimToIndex.length

function sortSub(arr, l, r, f) {
    var preSorted = arr.slice(0, l)
    var postSorted = arr.slice(r);
    var toSort = arr.slice(l, r).sort(f)
    return preSorted.concat(toSort).concat(postSorted)
}


function str_recur_leaf(x, left, right, dim, totalDim, blockCountPerSlice){
    if(dim < totalDim-1){
        sortSub(x, left, right, function (a, b) {
            return a[dim] - b[dim]
        })
        var i
        for (i = 0; i < N; i += blockCountPerSlice * B_leaf) {
            var itemCountPerSlice = blockCountPerSlice * B_leaf
            var end = (i + itemCountPerSlice) > N ? N : i + itemCountPerSlice
            x = str_recur_leaf(x, i, end)
        }
    }else{
        

    }
    

}

function packData(x){
    var N = x.length //# total data count
    var blockCount = Math.ceil(N / cfg.B_leaf)
    var sliceCount = Math.ceil(Math.pow(blockCount, (1 / cfg.K)))
    var blockCountPerSlice = Math.ceil(blockCount / sliceCount)
    var _DEBUG_segmentCount = sliceCount
    var _DEBUG_distinctValCount = _.uniq(x.map(function (i) {
        return i[0]
    })).length
      
    /* process.stdout.write(_DEBUG_distinctValCount+", "+_DEBUG_segmentCount+", ") */
    
    //find sub regions
    
    var leafNodes = []
    for (i = 0; i < N; i += B) {
        var end = (i + B) > N ? N : i + B
        leafNodes.push(leafNode(x, i, end))
    }
    return leafNodes
}

function packIndex(){

}

var levels = []

function RTree(data){
    var leafNodes = packData(data)
    levels.push(leafNodes)
    var indexNodes = leafNodes
    do {
        indexNodes = packIndex(indexNodes)
        levels.push(indexNodes)
    } while (indexNodes.length > 1)
    return indexNodes[0]
}

